알고리즘 복잡도 분석 (Big-O)

일반적으로 입력의 개수 𝑛과 시간 복잡도 함수 𝑇(𝑛)의 관계는 상당히 복잡할 수 있다. 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 Big-O 표기법이라고 한다. 예를들어 알고리즘이 𝑛에 비례하는 수행시간을 가진다고 말하는 대신 해당 알고리즘의 시간 복잡도가 𝑂(n)이라고 한다. 두 개의 함수 𝑓(𝑛)과 𝑔(𝑛)이 주어졌을 ...

알고리즘시간 복잡도자료구조Big OBig O

notation - 빅오 표기법

우리는 알고리즘 실행 효율성을 측정할 척도가 필요하고, Big-O 표기는 이를 수학적으로 표현해주는 표기법이다. Big-O 표기법은 해당 코드가 얼마나 수행되었는지(결과값을 출력하기 위한 연산을 얼마나 반복했는지)에 따라 효율성을 확인한다. Big-O 표기법은 데이터 입력값 크기에 따라 알고리즘 실행 속도의 변화를 설명하는 방법이다. 알고리즘 계산 복잡도 종류 시간 복잡도(time compl...

로그시간O(logn)Big O빅오표기법제곱시간O(n^2)space complexity공간복잡도선형시간ON상수시간시간복잡도algorithm알고리즘Time ComplexityO(1)Big O